#ifndef _BO2_1_H
#define _BO2_1_H
// bo2-1.h 顺序存储的线性表（存储结构由c2-1.h定义）的基本操作12个
void InitList(SqList &L)
{//操作结果：构造一个空的顺序线性表L
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem) //存储分配失败
        exit(OVERFLOW);
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
}

void DestroyList(SqList &L)
{//初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L
    free(L.elem);
    L.elem=NULL;
    L.length = 0;
    L.listsize = 0;
}

void ClearList(SqList &L)
{//初始条件：顺序线性表L已存在。操作结果：将L重置为空表
    L.length = 0;
}

Status ListEmpty(SqList L)
{//初始条件：顺序线性表L已存在。操作结果：判断L是否为空表，是则返回TRUE，否则返回FALSE
    if(L.length == 0)
        return TRUE;
    else
        return FALSE;
}

int ListLength(SqList L)
{//初始条件：顺序线性表L已存在。操作结果：返回L中数据元素的个数
    return L.length;
}

Status GetElem(SqList L, int i, ElemType &e)
{//初始条件：顺序线性表L已存在。1<=i<=Listlength(L)
//操作结果：用e返回L中第i个数据元素的值
    if(i<1 || i>L.length)
        return ERROR;
    e = *(L.elem + i - 1);
    return OK;
}

int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{//初始条件：顺序线性表L已存在。compare()是数据元素判定函数（满足为1，否则为0）
//操作结果：返回L中第一个与e满足关系compare（）的数据元素的位序。
//          若这样的数据元素不存在，则返回值为0.  严书算法2.6
    int i = 1; // i 的处置为第一个元素的位序
    ElemType * p = L.elem; // p 的初值为第一个元素的存储位置
    while(i <= L.length && !compare(*p++, e)) // i未超出表的范围且未找到满足关系的数据元素
        i++;
    if(i <= L.length)
        return i; //找到了，返回其位序
    else
        return 0; // 没找到
}

Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e)
{//初始条件：顺序线性表L已存在。
//操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱；
//          否则操作失败，pre_e无定义
    int i = 2; // 从第二个元素开始
    ElemType * p = L.elem + 1;
    while(i<=L.length && *p!=cur_e) //i未超出表的范围且未找到值为cur_e的元素
    {
        p++; // p指向下一个元素
        i++; //计数加1
    }
    if(i > L.length)
        return ERROR;
    else
    {
        pre_e = * --p;//p指向前一个元素（cur_e的前驱）
        return OK;
    }

}

Status NextElem(SqList L, ElemType cur_e, ElemType &next_e)
{
    int i = 1; // 从第一个元素开始
    ElemType * p = L.elem; //p指向第一个元素
    while( i < L.length && *p != cur_e) //i未超出表的范围且未找到值为cur_e的元素
    {
        p++; //p指向下一个元素
        i++; //计数加1
    }
    if(i == L.length)
        return ERROR;
    else
    {
        next_e = * ++p;
        return OK;
    }
}

Status ListInsert(SqList &L, int i, ElemType e)//算法2.4
{//初始条件：L已存在， 1<= i <=L.length+1
//操作结果： 在L中第i个位置之前 插入新的数据元素e，L的长度+1
    ElemType * newbase, *q ,*p;
    if(i < 1 || i > L.length+1) //i值不合法
        return ERROR;
    if(L.length == L.listsize) // 当前存储空间已满，增加分配
    {
        newbase = (ElemType*)realloc(L.elem, (L.listsize+LIST_INCREMENT) * sizeof(ElemType));
        if(!newbase)
            exit(OVERFLOW);
        L.elem = newbase; // 新基地址赋给L.elem
        L.listsize += LIST_INCREMENT;
    }
    q = L.elem + i - 1; // q为插入位置
    for(p = L.elem + L.length - 1; p >= q; p--)//把插入位置及之后的元素全部往后移动，从表尾开始移动
        *(p+1) = *p; //后移动
    *q = e; //插入e
    L.length++; //表长度+1
    return OK;
}

Status ListDelete(SqList &L, int i, ElemType &e)
{//初始条件：L已存在， 1<= i <=L.length
//操作结果：删除L的第i个元素，用e返回其值，L的长度减1
    ElemType * p, *q;
    if(i < 1 || i > L.length)
        return ERROR;
    p = L.elem + i - 1;//p为被删除元素的位置
    e = *p; // 被删除元素的值赋给e
    q = L.elem + L.length - 1; // q为表尾元素位置
    for(p=p+1;p <= q; p++) // 被删除的元素之后全部往前移动， 从被删除的位置开始
         *(p-1) = *p;
    L.length--;
    return OK;
}

void ListTraverse(SqList L, void(*visit)(ElemType&))
{//初始条件：L已存在
//操作结果:以此对L的每个数据元素调用函数visit()
//      visit的形参加&，表明可是通过调用visit改变元素的值
    ElemType * p = L.elem; //p指向第一个元素
    for(int i = 1; i <= L.length; i++)
        visit(*p++); //对每个数据元素调用visit（）
    printf("\n");
}

#endif